package binary_tree.LeetCode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 二叉树中序遍历的迭代写法
 */
public class Num94 {
    public List<Integer> inorderTraversal(TreeNode root) {
          List<Integer> ret=new ArrayList<>();
          if(root==null){
              return ret;
          }
        Deque<TreeNode> stack=new ArrayDeque<>();
          TreeNode r1=root;
          while (r1!=null||!stack.isEmpty()){
              //先一路向左走到底
              while (r1!=null){
                  stack.push(r1);
                  r1=r1.left;
              }
              //此时r1为空，弹出栈顶元素，也就是第一个左子树为空的节点
              r1=stack.poll();
              ret.add(r1.val);
              //此时继续访问右子树
              r1=r1.right;
          }
          return ret;
    }
}
